package com.bee.剑指offer;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 请实现两个函数，分别用来序列化和反序列化二叉树，不对序列化之后的字符串进行约束，
 * 但要求能够根据序列化之后的字符串重新构造出一棵与原二叉树相同的树。
 */
public class 序列化二叉树 {

    private static TreeNode em = new TreeNode(-1);

    /**
     * 使用层序遍历进行序列化
     */
    static String Serialize(TreeNode root) {
        StringBuilder str = new StringBuilder();
        if (root == null) {
            return "";
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode poll = queue.poll();
                if (poll.val == -1) {
                    str.append("#,");
                } else {
                    str.append(poll.val);
                    str.append(",");
                }
                if (!poll.equals(em)) {
                    queue.offer(poll.left == null ? em : poll.left);
                    queue.offer(poll.right == null ? em : poll.right);
                }
            }
        }
        int i = str.lastIndexOf(",");
        return str.toString();
    }

    /**
     * 利用队列进行构建
     */
    static TreeNode Deserialize(String str) {
        if (str.equals("")) {
            return null;
        }
        String[] split = str.split(",");
        if (split.length <= 0) {
            return null;
        }
        Queue<TreeNode> queue = new ArrayDeque<>();
        TreeNode root = new TreeNode(Integer.parseInt(split[0]));
        queue.offer(root);
        for (int i = 1; i < split.length - 1; i += 2) {
            TreeNode poll = queue.poll();
            if (!split[i].equals("#")) {
                poll.left = new TreeNode(Integer.parseInt(split[i]));
                queue.offer(poll.left);
            }
            if (!split[i + 1].equals("#")) {
                poll.right = new TreeNode(Integer.parseInt(split[i + 1]));
                queue.offer(poll.right);
            }
        }
        return root;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);

        String serialize = Serialize(root);
        System.out.println(serialize);
        TreeNode deserialize = Deserialize("1,2,3,#,#,6,7,#,#,#,#,");
        System.out.println(deserialize.val);

    }
}
